﻿#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>

using namespace std;

//--------------------------------------------------------双指针----------------------------------------------------------

// 移动零

//算法流程：
//a.初始化 cur = 0 （⽤来遍历数组）， dest = -1 
//（指向⾮零元素序列的最后⼀个位置。因为刚开始我们不知道最后⼀个⾮零元素在什么位置，因此初始化为 - 1 ）
//b.cur 依次往后遍历每个元素，遍历到的元素会有下⾯两种情况：
//    i.遇到的元素是 0 ， cur 直接 ++ 。
//    因为我们的⽬标是让[dest + 1, cur - 1] 内的元素全都是零，因此当 cur 遇到 0 的时候，直接 ++ ，就可以让 0 在 cur - 1的位置上，从⽽在[dest + 1, cur - 1] 内；
//    ii.遇到的元素不是 0 ， dest++ ，并且交换 cur 位置和 dest 位置的元素，之后让cur++ ，扫描下⼀个元素。
//    • 因为 dest 指向的位置是⾮零元素区间的最后⼀个位置，如果扫描到⼀个新的⾮零元素，那么它的位置应该在 dest + 1 的位置上，因此 dest 先⾃增 1 ；
//    • dest++ 之后，指向的元素就是 0 元素（因为⾮零元素区间末尾的后⼀个元素就是0 ），
//    因此可以交换到 cur 所处的位置上，实现[0, dest] 的元素全部都是⾮零元素，[dest + 1, cur - 1] 的元素全是零。

class Solution {
public:
    void moveZeroes(vector<int>& nums)
    {
        int cur = 0, dest = -1;
        while (cur <= nums.size() - 1)
        {
            while (cur < nums.size() && nums[cur] == 0)
            {
                cur++;
            }
            if (cur < nums.size() && nums[cur] != 0)
            {
                swap(nums[cur++], nums[++dest]);
            }
        }
    }
};

// 复写零

//算法思路：
//如果「从前向后」进⾏原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数「被覆盖掉」。
//因此我们选择「从后往前」的复写策略。
//但是「从后向前」复写的时候，我们需要找到「最后⼀个复写的数」，因此我们的⼤体流程分两步：
//i.先找到最后⼀个复写的数；
//ii.然后从后向前进⾏复写操作。

class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int dest = -1, cur = 0;
        while (cur < arr.size())
        {
            if (arr[cur] != 0)
            {
                ++dest;
            }
            else
            {
                dest += 2;
            }
            if (dest >= arr.size() - 1)
            {
                break;
            }
            cur++;
        }
        if (dest == arr.size())
        {
            arr[arr.size() - 1] = 0;
            dest -= 2;
            cur--;
        }
        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = arr[dest--] = 0;
                cur--;
            }
        }
    }
};


//快乐数

//算法思路：
//根据上述的题⽬分析，我们可以知道，当重复执⾏ x 的时候，数据会陷⼊到⼀个「循环」之中。
//⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。
//如果相遇位置的值是 1 ，那么这个数⼀定是快乐数；如果相遇位置不是 1的话，那么就不是快乐数。
//
//补充知识：如何求⼀个数 n 每个位置上的数字的平⽅和。
//a.把数 n 每⼀位的数提取出来：
//  循环迭代下⾯步骤：
//  i. int t = n % 10 提取个位；
//  ii.n /= 10 ⼲掉个位；
//      直到 n 的值变为 0 ；
//b.提取每⼀位的时候，⽤⼀个变量 tmp 记录这⼀位的平⽅与之前提取位数的平⽅和
//  ▪ tmp = tmp + t * t

class Solution {
public:
    int besqrt(int n)
    {
        int s = 0;
        while (n)
        {
            int t = n % 10;
            s += t * t;
            n /= 10;
        }
        return s;
    }
    bool isHappy(int n)
    {
        int slow = n, fast = besqrt(n);
        while (slow != fast)
        {
            slow = besqrt(slow);
            fast = besqrt(besqrt(fast));
        }
        return slow == 1;
    }
};


//盛⽔最多的容器

//设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 :
//v = (right - left) * min(height[right], height[left])
//容器的左边界为 height[left] ，右边界为 height[right] 。
//为了⽅便叙述，我们假设「左边边界」⼩于「右边边界」。
//如果此时我们固定⼀个边界，改变另⼀个边界，⽔的容积会有如下变化形式：
//◦ 容器的宽度⼀定变⼩。
//◦ 由于左边界较⼩，决定了⽔的⾼度。如果改变左边界，新的⽔⾯⾼度不确定，但是⼀定不会超
//过右边的柱⼦⾼度，因此容器的容积可能会增⼤。
//◦ 如果改变右边界，⽆论右边界移动到哪⾥，新的⽔⾯的⾼度⼀定不会超过左边界，也就是不会
//超过现在的⽔⾯⾼度，但是由于容器的宽度减⼩，因此容器的容积⼀定会变⼩的。
//由此可⻅，左边界和其余边界的组合情况都可以舍去。
//所以我们可以 left++ 跳过这个边界，继续去判断下⼀个左右边界。


class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int l = 0, r = height.size() - 1;
        int tmp = 0;
        while (l < r)
        {
            int water = (r - l) * min(height[l], height[r]);
            tmp = max(tmp, water);
            if (height[l] > height[r])
            {
                r--;
            }
            else
            {
                l++;
            }
        }
        return tmp;
    }
};


//有效三角形的个数

//先将数组排序。
// 
//根据「解法⼀」中的优化思想，我们可以固定⼀个「最⻓边」，
// 然后在比这条边小的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。
// 由于数组是有序的，我们可以利⽤「对撞指针」来优化。
// 
//设最⻓边枚举到 i 位置，区间[left, right] 是 i 位置左边的区间（也就是⽐它⼩的区间）：
// 
//◦ 如果 nums[left] + nums[right] > nums[i] ：
//▪ 说明[left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐nums[i] ⼤的⼆元组
//▪ 满⾜条件的有 right - left 种
//▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断
// 
//◦ 如果 nums[left] + nums[right] <= nums[i] ：
//▪ 说明 left 位置的元素是不可能与[left + 1, right] 位置上的元素构成满⾜条件⼆元组
//▪ left 位置的元素可以舍去， left++ 进⼊下轮循环

class Solution {
public:
    int triangleNumber(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = nums.size() - 1; i >= 2; i--)
        {
            int l = 0, r = i - 1;
            while (l < r)
            {
                if (nums[l] + nums[r] > nums[i])
                {
                    count += (r - l);
                    r--;
                }
                else
                {
                    l++;
                }
            }
        }
        return count;
    }
};



//和为 s 的两个数字

//初始化 left ， right 分别指向数组的左右两端
// 
//b.当 left < right 的时候，⼀直循环
//    i.当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回；
//    ii.当 nums[left] + nums[right] < target 时,
//    left++
//    iii.当 nums[left] + nums[right] > target 时，
//    right-- 

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target)
    {
        int n = price.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            if (price[l] + price[r] < target)
            {
                l++;
            }
            else if (price[l] + price[r] > target)
            {
                r--;
            }
            else
            {
                return { price[l],price[r] };
            }
        }
        return { -1,-1 };
    }
};


//三数之和

// i.先排序；
// 第一个数已经是整数，后面的肯定也是，所以这个数组没有三数之和==0
// ii.然后找到 nums[i] + nums[l] == -nums[r]

// 
//「去重」
//i.找到⼀个结果之后， left 和 right 指针要「跳过重复」的元素；
//ii.当使⽤完⼀次双指针算法之后，固定的 nums[i] 也要「跳过重复」的元素。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());

        for (int i = 0; i < n; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            if (nums[i] > 0)
                break;
            while (l < r)
            {
                while (l < r && nums[i] + nums[l] == -nums[r])
                {
                    ret.push_back({ nums[i],nums[l],nums[r] });
                    while (l < r && nums[l] == nums[l + 1]) ++l;
                    while (l < r && nums[r] == nums[r - 1]) --r;
                    l++; r--;
                }
                while (l < r && nums[i] + nums[l] < -nums[r])
                {
                    l++;
                }
                while (l<r && nums[i] + nums[l]>-nums[r])
                {
                    r--;
                }
            }
        }
        return ret;
    }
};


//四数之和

//思路
//a.依次固定⼀个数 num[i] ；
//b.在这个数 a 的后⾯区间上，利⽤「三数之和」找到三个数，使这三个数的和等于 target - num[i] 即可。


class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        if (n < 4) return ret;
        for (int i = 0; i < n; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n; j++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int l = j + 1, r = n - 1;
                while (l < r)
                {
                    long long s = (long long)nums[l] + nums[r] + nums[i] + nums[j];
                    if (l < r && s == target)
                    {
                        ret.push_back({ nums[i],nums[j],nums[l],nums[r] });
                        while (l < r && nums[l] == nums[l + 1])l++;
                        while (l < r && nums[r] == nums[r - 1])r--;
                        l++;
                        r--;
                    }
                    if (l < r && s < target)l++;
                    if (l<r && s>target)r--;
                }
            }
        }
        return ret;
    }
};


//----------------------------------------------------------滑动窗口-------------------------------------------------------

//⻓度最⼩的⼦数组（medium）

//让滑动窗⼝满⾜：从 i 位置开始，窗⼝内所有元素的和⼩于 target 
// （那么当窗⼝内元素之和第一次大于等于⽬标值的时候，就是 i 位置开始，满⾜条件的最⼩⻓度）
// 
//做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：
//▪ 如果窗⼝内元素之和⼤于等于 target ：更新结果，并且将左端元素划出去的同时继续判
//断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）
//▪ 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。


class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int n = nums.size();
        int len = INT_MAX;
        int sum = 0;
        int l = 0;
        for (int r = 0; r < n; r++)
        {
            sum += nums[r];
            while (sum >= target)
            {
                len = min(len, (r - l + 1));
                sum -= nums[l]; l++;
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};


//⽆重复字符的最⻓⼦串

//让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。
//做法：右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：
//▪ 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，
//直到 ch 这个元素的频次变为 1 ，然后再更新结果。
//▪ 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果


class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_map<char, int> hash;
        int n = s.size();
        int len = 0;
        int l = 0, r = 0;
        while (r < n)
        {
            hash[s[r]]++;
            while (hash[s[r]] > 1)
            {
                hash[s[l++]]--;
            }
            len = max(len, r - l + 1);
            r++;
        }
        return len;
    }
};


//最⼤连续 1 的个数 III

//a.初始化⼀个大小为 2 的数组就可以当做哈希表 hash 了；
// 初始化一些变量 left = 0,right = 0, ret = 0 ；

//b.当 right ⼩于数组大小的时候，⼀直下列循环：
//i.让当前元素进⼊窗⼝，顺便统计到哈希表中；
//ii.检查 0 的个数是否超标：
//• 如果超标，依次让左侧元素滑出窗⼝，顺便更新哈希表的值，直到 0 的个数恢复正常；
//iii.程序到这⾥，说明窗⼝内元素是符合要求的，更新结果；
//iv.right++ ，处理下⼀个元素；

//c.循环结束后， ret 存的就是最终结果。


class Solution {
public:
    int longestOnes(vector<int>& nums, int k)
    {
        int n = nums.size();
        unordered_map<int, int> hash;
        int l = 0, r = 0, len = 0;
        while (r < n)
        {
            hash[nums[r]]++;
            while (hash[0] > k)
            {
                hash[nums[l++]]--;
            }
            len = max(len, r - l + 1);
            r++;
        }
        return len;
    }
};



//将 x 减到 0 的最⼩操作数

//    a.转化问题：求 target = sum(nums) - x 。如果 target < 0 ，问题无解；
//    b.初始化左右指针 l = 0, r = 0 
// （滑动窗⼝区间表⽰为[l, r) ，左右区间是否开闭很重要，必须设定与代码⼀致），
// 记录当前滑动窗⼝内数组和的变量 sum = 0 ，记录当前满⾜条件数组的最⼤区间⻓度 maxLen = -1 ；
// 
//    c.当 r ⼩于等于数组⻓度时，一直循环：
//    i.如果 sum < target ，右移右指针，直⾄变量和⼤于等于 target ，或右指针已经移到
//    头；
//    ii.如果 sum > target ，右移左指针，直⾄变量和⼩于等于 target ，或左指针已经移到
//    头；
//    iii.如果经过前两步的左右移动使得 sum == target ，维护满⾜条件数组的最⼤⻓度，并让下个元素进入窗⼝；

//    d.循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回 - 1 。



class Solution {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = nums.size();
        int sum = 0, l = 0, r = 0;
        for (auto a : nums)
        {
            sum += a;
        }
        int target = sum - x;
        if (target < 0)return -1;
        int len = -1, ss = 0;
        for (r = 0; r < n; ++r)
        {
            ss += nums[r];
            while (l <= r && ss > target)
            {
                ss -= nums[l++];
            }
            if (ss == target)
            {
                len = max(len, r - l + 1);
            }
        }
        return len == -1 ? -1 : (n - len);
    }
};


//⽔果成篮

//a.初始化哈希表 hash 来统计窗⼝内⽔果的种类和数量；
//b.初始化变量：左右指针 left = 0，right = 0，记录结果的变量 ret = 0；
//c.当 right ⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
//i.将当前⽔果放入哈希表中；
//ii.判断当前⽔果进来后，哈希表的⼤⼩：
//• 如果超过 2：
//◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；
//◦ 如果这个元素的频次减⼀之后变成了 0，就把该元素从哈希表中删除；
//◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过 2；
//iii.更新结果 ret；
//iv.right++，让下⼀个元素进⼊窗⼝；
//d.循环结束后，ret 存的就是最终结果


class Solution {
public:
    int totalFruit(vector<int>& fruits)
    {
        int n = fruits.size();
        unordered_map<int, int> hash;
        if (n <= 2)return n;
        int l = 0, r = 0, len = 0;
        while (r < n)
        {
            hash[fruits[r]]++;
            while (hash.size() > 2)
            {
                hash[fruits[l]]--;
                if (hash[fruits[l]] == 0)
                {
                    hash.erase(fruits[l]);
                }
                l++;
            }
            len = max(len, r - l + 1);
            r++;
        }
        return len;
    }
};


// 找到字符串中所有字⺟异位词

//因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，、
// 所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字母的数量；
//◦ 当窗⼝中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗⼝为字符串 p的异位词；
//◦ 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表
// ⼀个来保存 s 中的⼦串每个字符出现的个数
// 另⼀个来保存 p 中每⼀个字符出现的个数。
// 这样就能判断两个串是否是异位词。

//是否是异位词  --  比较字母的数量是否一致
//用count作为有效字母进入滑动窗口的个数 当个数等于p时 就是异位词


class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;
        int m = s.size(), n = p.size();
        if (m < n)return ret;
        int hash1[26] = { 0 };
        int hash2[26] = { 0 };
        for (auto a : p)
        {
            hash1[a - 'a']++;
        }
        int count = 0, l = 0, r = 0;
        while (r < m)
        {
            hash2[s[r] - 'a']++;
            if (hash2[s[r] - 'a'] <= hash1[s[r] - 'a'])count++;
            if (r - l + 1 > n)
            {
                if (hash2[s[l] - 'a'] <= hash1[s[l] - 'a'])count--;
                hash2[s[l] - 'a']--; l++;
            }
            if (count == n)ret.push_back(l); r++;
        }
        return ret;
    }
};



//串联所有单词的⼦串

//如果我们把每⼀个单词看成⼀个⼀个字母，问题就变成了找到「字符串中所有的字母异位词」。
//无非就是之前处理的对象是⼀个⼀个的字符，我们这⾥处理的对象是⼀个⼀个的单词。

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        int m = s.size();
        int n = words[0].size();
        int len = words.size();
        vector<int> ret;
        unordered_map<string, int> hash1;
        for (auto ss : words)
        {
            hash1[ss]++;
        }

        for (int i = 0; i < n; i++)
        {
            int l = i, r = i, count = 0;
            unordered_map<string, int> hash2;//记得要清空hash2！！！
            while (r + n <= m)
            {
                hash2[s.substr(r, n)]++;
                if (hash1.count(s.substr(r, n)) && hash2[s.substr(r, n)] <= hash1[s.substr(r, n)])count++;
                if (r - l + 1 > len * n)
                {
                    if (hash1.count(s.substr(l, n)) && hash2[s.substr(l, n)] <= hash1[s.substr(l, n)])count--;
                    hash2[s.substr(l, n)]--; l += n;
                }
                if (len == count)
                {
                    ret.push_back(l);
                }
                r += n;
            }
        }
        return ret;
    }
};


//最⼩覆盖⼦串

//a.定义两个全局的哈希表：
// 1 号哈希表 hash1 ⽤来记录子串的信息， 2 号哈希表 hash2用来记录⽬标串 t 的信息；
//b.实现⼀个接⼝函数，判断当前窗口是否满⾜要求：
//i.遍历两个哈希表中对应位置的元素：
//• 如果 t 中某个字符的数量⼤于窗⼝中字符的数量，也就是 2 号哈希表某个位置⼤于1 号哈希表。
// 说明不匹配，返回 false ；
// 如果全都匹配，返回 true 。

//主函数中：
//a.先将 t 的信息放⼊ 2 号哈希表中；
//b.初始化⼀些变量：左右指针： left = 0，right = 0 ；⽬标⼦串的⻓度： len =INT_MAX ；
// ⽬标⼦串的起始位置： retleft ；（通过⽬标⼦串的起始位置和⻓度，我们就能找到结果）
//c.当 right ⼩于字符串 s 的⻓度时，⼀直下列循环：
//i.将当前遍历到的元素扔进 1 号哈希表中；
//ii.检测当前窗⼝是否满⾜条件：
//• 如果满⾜条件：
//◦ 判断当前窗⼝是否变⼩。如果变⼩：更新⻓度 len ，以及字符串的起始位置retleft ；
//◦ 判断完毕后，将左侧元素滑出窗⼝，顺便更新 1 号哈希表；
//◦ 重复上⾯两个过程，直到窗⼝不满⾜条件；
//iii.right++ ，遍历下⼀个元素；
//d.判断 len 的⻓度是否等于 INT_MAX ：
//i.如果相等，说明没有匹配，返回空串；
//ii.如果不想等，说明匹配，返回 s 中从 retleft 位置往后 len ⻓度的字符串。



class Solution {
public:
    string minWindow(string s, string t)
    {
        int m = s.size();
        int n = t.size();
        int hash1[128] = { 0 };
        int len = 0;
        for (auto tt : t)
        {
            if (hash1[tt] == 0)len++;//记录t的有效字母的种类（不是个数！）
            hash1[tt]++;
        }
        int hash2[128] = { 0 };
        int minlen = INT_MAX;
        int beginl = -1;
        for (int l = 0, r = 0, count = 0; r < m; r++)
        {
            char in = s[r];
            hash2[in]++;//进窗口
            if (hash2[in] == hash1[in])count++;//维护count
            while (count == len)
            {
                if (r - l + 1 < minlen)//要先更新结果再出窗口
                {
                    minlen = r - l + 1;
                    beginl = l;
                }
                char out = s[l];
                if (hash1[out] == hash2[out])count--;
                hash2[out]--; l++;
            }
        }
        if (beginl == -1)
        {
            return "";
        }
        else
        {
            return s.substr(beginl, minlen);
        }
    }
};

//------------------------------------------------------二分查找--------------------------------------------------------

//⼆分查找

//a.定义 left ， right 指针，分别指向数组的左右区间。
//b.找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
//    i.arr[mid] == target 说明正好找到，返回 mid 的值；
//    ii.arr[mid] > target 说明[mid, right] 这段区间都是⼤于 target 的，因此舍去右边区间，
//        在左边[left, mid - 1] 的区间继续查找，即让 right = mid -1 ，然后重复 2 过程；
//    iii.arr[mid] < target 说明[left, mid] 这段区间的值都是⼩于 target 的，因此舍去左边区间，
//        在右边[mid + 1, right] 区间继续查找，即让 left = mid +1 ，然后重复 2 过程；
//c.当 left 与 right 错开时，说明整个区间都没有这个数，返回 - 1 。

class Solution {
public:
    int search(vector<int>& nums, int target)
    {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l <= r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target)return mid;
            else if (nums[mid] > target)r = mid - 1;
            else l = mid + 1;
        }
        return -1;
    }
};


// 在排序数组中查找元素的第⼀个和最后⼀个位置

//算法思路：
//⽤的还是⼆分思想，就是根据数据的性质，在某种判断条件下将区间⼀分为⼆，然后舍去其中⼀个
//区间，然后再另⼀个区间内查找；
//⽅便叙述，⽤ x 表⽰该元素， resLeft 表⽰左边界， resRight 表⽰右边界。
//寻找左边界思路：
//• 寻找左边界：
//◦ 我们注意到以左边界划分的两个区间的特点：
//▪ 左边区间[left, resLeft - 1] 都是⼩于 x 的；
//▪ 右边区间（包括左边界）[resLeft, right] 都是⼤于等于 x 的；
//• 因此，关于 mid 的落点，我们可以分为下⾯两种情况：
//◦ 当我们的 mid 落在[left, resLeft - 1] 区间的时候，也就是 arr[mid] <
//    target 。说明[left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，
//    继续在[mid + 1, right] 上寻找左边界；
//    ◦ 当 mid 落在[resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。
//    说明[mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时
//    更新 right 到 mid 的位置，继续在[left, mid] 上寻找左边界；
//    • 由此，就可以通过⼆分，来快速寻找左边界；
//    注意：这⾥找中间元素需要向下取整。
//    因为后续移动左右指针的时候：
//    • 左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩⼩的；
//    • 右指针： right = mid ，可能会原地踏步（⽐如：如果向上取整的话，如果剩下 1, 2 两个元
//    素， left == 1 ， right == 2 ， mid == 2 。更新区间之后， left，right，mid 的值没有改变，就会陷⼊死循环）。
//    因此⼀定要注意，当 right = mid 的时候，要向下取整。
//    寻找右边界思路：
//    • 寻右左边界：
//    ◦ ⽤ resRight 表⽰右边界；
//    ◦ 我们注意到右边界的特点：
//    ▪ 左边区间 （包括右边界）[left, resRight] 都是⼩于等于 x 的；
//    ▪ 右边区间[resRight + 1, right] 都是⼤于 x 的；
//    • 因此，关于 mid 的落点，我们可以分为下⾯两种情况：
//    ◦ 当我们的 mid 落在[left, resRight] 区间的时候，说明[left, mid - 1]
//    （ mid 不可以舍去，因为有可能是最终结果） 都是可以舍去的，此时更新 left 到 mid
//    的位置 ◦ 当 mid；落在[resRight + 1, right] 的区间的时候，说明[mid, right] 内的元素
//    是可以舍去的，此时更新 right 到 mid - 1 的位置；
//    • 由此，就可以通过⼆分，来快速寻找右边界；
//    注意：这⾥找中间元素需要向上取整。
//    因为后续移动左右指针的时候：
//    • 左指针： left = mid ，可能会原地踏步（⽐如：如果向下取整的话，如果剩下 1, 2 两个元
//    素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值没有改变，就会陷⼊死循环）。
//    • 右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩⼩的；
//    因此⼀定要注意，当 right = mid 的时候，要向下取整。
//    ⼆分查找算法总结：

//    请⼤家⼀定不要觉得背下模板就能解决所有⼆分问题。⼆分问题最重要的就是要分析题意，然后确定
//    要搜索的区间，根据分析问题来写出⼆分查找算法的代码。
//    要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解
//    要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解
//    要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解
//    重要的事情说三遍。
//    模板记忆技巧：
//    1. 关于什么时候⽤三段式，还是⼆段式中的某⼀个，⼀定不要强⾏去⽤，⽽是通过具体的问题分析情
//    况，根据查找区间的变化确定指针的转移过程，从⽽选择⼀个模板。
//    2. 当选择两段式的模板时：
//    ◦ 在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 + 1 取中间数）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int begin = 0, end = 0;
        int n = nums.size();
        if (n == 0)return { -1,-1 };
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        if (nums[l] != target)return { -1,-1 };
        else begin = l;

        l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l + 1) / 2;
            if (nums[mid] <= target)
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        if (nums[l] != target)return { -1,-1 };
        else end = l;
        return { begin,end };
    }
};

//搜索插⼊位置

//a.分析插入位置左右两侧区间上元素的特点：
//设插⼊位置的坐标为 index ，根据插⼊位置的特点可以知道：
//•[left, index - 1] 内的所有元素均是⼩于 target 的；
//•[index, right] 内的所有元素均是大于等于 target 的。
//b.设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下⼀轮查询的区间：
//▪ 当 nums[mid] >= target 时，说明 mid 落在了[index, right] 区间上，
//mid 左边包括 mid 本⾝，可能是最终结果，所以我们接下来查找的区间在[left,mid] 上。
//因此，更新 right 到 mid 位置，继续查找。
//▪ 当 nums[mid] < target 时，说明 mid 落在了[left, index - 1] 区间上，
//    mid 右边但不包括 mid 本⾝，可能是最终结果，所以我们接下来查找的区间在[mid+ 1, right] 上。
//    因此，更新 left 到 mid + 1 的位置，继续查找。
//    c.直到我们的查找区间的⻓度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果。


class Solution {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
            // int mid=l+(r-l+1)/2;
            // if(nums[mid]<=target)
            // {
            //     l=mid;
            // }
            // else
            // {
            //     r=mid-1;
            // }
        }
        if (nums[r] < target)return r + 1;
        else return r;
        // if(nums[l]<target)return l+1;
        // else return l;
    }
};

//x 的平⽅根

//设 x 的平⽅根的最终结果为 index ：
//a.分析 index 左右两次数据的特点：
//▪[0, index] 之间的元素，平⽅之后都是⼩于等于 x 的；
//▪[index + 1, x] 之间的元素，平⽅之后都是⼤于 x 的。
//因此可以使⽤⼆分查找算法。

class Solution {
public:
    int mySqrt(int x)
    {
        if (x < 1)return 0;
        int l = 1, r = x;
        while (l < r)
        {
            long long mid = l + (r - l + 1) / 2;
            if (mid * mid <= x)
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        return l;
    }
};


//⼭峰数组的峰顶

//1. 分析峰顶位置的数据特点，以及⼭峰两旁的数据的特点：
//  ◦ 峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
//  ◦ 峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈现上升趋势；
//  ◦ 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。
//2. 因此，根据 mid 位置的信息，我们可以分为下⾯三种情况：
//    ◦ 如果 mid 位置呈现上升趋势，说明我们接下来要在[mid + 1, right] 区间继续搜索；
//    ◦ 如果 mid 位置呈现下降趋势，说明我们接下来要在[left, mid - 1] 区间搜索；
//    ◦ 如果 mid 位置就是⼭峰，直接返回结果。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr)
    {
        int n = arr.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (arr[mid] > arr[mid - 1])
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return l - 1;
    }
};



//寻找峰值

//算法思路：
//寻找⼆段性：
//任取⼀个点 i ，与下⼀个点 i + 1 ，会有如下两种情况:
//• arr[i] > arr[i + 1] : 此时「左侧区域」⼀定会存在⼭峰（因为最左侧是负⽆穷），那么我们可以去左侧去寻找结果；
//• arr[i] < arr[i + 1] : 此时「右侧区域」⼀定会存在⼭峰（因为最右侧是负⽆穷），那么我们可以去右侧去寻找结果。
//当我们找到「⼆段性」的时候，就可以尝试⽤「⼆分查找」算法来解决问题。

class Solution {
public:
    int findPeakElement(vector<int>& nums)
    {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid + 1] > nums[mid])
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return l;
    }
};


//搜索旋转排序数组中的最⼩值

//其中 C 点就是我们要求的点。
//⼆分的本质：找到⼀个判断标准，使得查找区间能够⼀分为⼆。
//通过图像我们可以发现，[A，B] 区间内的点都是严格⼤于 D 点的值的， C 点的值是严格⼩于 D 点的值的。
//但是当[C，D] 区间只有⼀个元素的时候， C 点的值是可能等于 D 点的值的。
//因此，初始化左右两个指针 left ， right ：
//然后根据 mid 的落点，我们可以这样划分下⼀次查询的区间：
//▪ 当 mid 在[A，B] 区间的时候，也就是 mid 位置的值严格⼤于 D 点的值，下⼀次查询区间在[mid + 1，right] 上；
//▪ 当 mid 在[C，D] 区间的时候，也就是 mid 位置的值严格⼩于等于 D 点的值，下次查询区间在[left，mid] 上。
//当区间⻓度变成 1 的时候，就是我们要找的结果


class Solution {
public:
    int findMin(vector<int>& nums)
    {
        int n = nums.size();
        int l = 0, r = n - 1;
        int x = nums[r];
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] > x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return nums[l];
    }
};



//0~n-1 中缺失的数字

//关于这道题中，时间复杂度为 O(N) 的解法有很多种，⽽且也是⽐较好想的，这⾥就不再赘述。
//本题只讲解⼀个最优的⼆分法，来解决这个问题。
//在这个升序的数组中，我们发现：
//▪ 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
//▪ 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。
//因此，我们可以利⽤这个「⼆段性」，来使⽤「⼆分查找」算法。

class Solution {
public:
    int takeAttendance(vector<int>& records)
    {
        int n = records.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (records[mid] > mid)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l == records[l] ? l + 1 : l;
    }
};


//---------------------------------------------------前缀和--------------------------------------------------------------

//【模板】⼀维前缀和

//a.先预处理出来⼀个「前缀和」数组：
//⽤ dp[i] 表⽰：[1, i] 区间内所有元素的和，那么 dp[i - 1] ⾥⾯存的就是[1,i - 1] 区间内所有元素的和，
//那么：可得递推公式： dp[i] = dp[i - 1] + arr[i]
//b.使⽤前缀和数组，「快速」求出「某⼀个区间内」所有元素的和：
//当询问的区间是[l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1] 。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0;
    cin >> n >> m;
    vector<long long> a(n + 1, 0);
    vector<long long> dp(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dp[1] = a[1];
    int x = 0, y = 0;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        cout << dp[y] - dp[x - 1] << endl;
    }

    return 0;
}


//【模板】⼆维前缀和


#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1));
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    int x1 = 0, x2 = 0, y1 = 0, y2 = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
        }
    }
    for (int i = 0; i < q; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }


    return 0;
}


//寻找数组的中⼼下标

//从中心下标的定义可知，除中心下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。
//▪ 因此，我们可以先预处理出来两个数组，⼀个表⽰前缀和，另⼀个表⽰后缀和。
//▪ 然后，我们可以⽤⼀个 for 循环枚举可能的中⼼下标，判断每⼀个位置的「前缀和」以及
//「后缀和」，如果⼆者相等，就返回当前下标。

class Solution {
public:
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> dp1(n);
        vector<int> dp2(n);

        for (int i = 1; i < n; i++)//前i-1数组的和（不包括自己）
        {
            dp1[i] = dp1[i - 1] + nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--)//后几个数之和（不包括自己）
        {
            dp2[i] = dp2[i + 1] + nums[i + 1];
        }
        for (int i = 0; i < n; i++)
        {
            if (dp1[i] == dp2[i])
            {
                return i;
            }
        }
        return -1;
    }
};


//除⾃⾝以外数组的乘积

//注意题⽬的要求，不能使⽤除法，并且要在 O(N) 的时间复杂度内完成该题。
//那么我们就不能使⽤暴⼒的解法，以及求出整个数组的乘积，然后除以单个元素的⽅法。
//继续分析，根据题意，对于每⼀个位置的最终结果 ret[i] ，它是由两部分组成的：
//i.nums[0] * nums[1] * nums[2] * ... * nums[i - 1]
//ii.nums[i + 1] * nums[i + 2] * ... * nums[n - 1]
//于是，我们可以利⽤前缀和的思想，使⽤两个数组 post 和 suf，分别处理出来两个信息：
//i.post 表⽰：i 位置之前的所有元素，即[0, i - 1] 区间内所有元素的前缀乘积，
//ii.suf 表⽰： i 位置之后的所有元素，即[i + 1, n - 1] 区间内所有元素的后缀乘积
//然后再处理最终结果。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret(n);
        vector<int> dp1(n);
        vector<int> dp2(n);
        dp1[0] = 1, dp2[n - 1] = 1;
        for (int i = 1; i < n; i++)
        {
            dp1[i] = (dp1[i - 1] * nums[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--)
        {
            dp2[i] = (dp2[i + 1] * nums[i + 1]);
        }
        for (int i = 0; i < n; i++)
        {
            ret[i] += dp1[i] * dp2[i];
        }
        return ret;
    }
};


//和为 k 的⼦数组

//设 i 为数组中的任意位置，⽤ sum[i] 表⽰[0, i] 区间内所有元素的和。
//想知道有多少个「以 i 为结尾的和为 k 的⼦数组」，就要找到有多少个起始位置为 x1, x2,x3... 
//使得[x, i] 区间内的所有元素的和为 k 。那么[0, x] 区间内的和是不是就是sum[i] - k 了。
// 于是问题就变成：
//找到在[0, i - 1] 区间内，有多少前缀和等于 sum[i] - k 的即可。
//我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，有多少个前缀和等于sum[i] - k 。
//因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;//第一个是前缀和，第二个是和的个数
        int sum = 0, ret = 0;
        hash[0] = 1;
        for (auto x : nums)
        {
            sum += x;
            if (hash.count(sum - k))ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};


//和可被 K 整除的⼦数组

//本题需要的前置知识：
// 同余定理
//如果(a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。
// ⽤⽂字叙述就是，如果两个数相减的差能被 n 整除，那么这两个数对 n 取模的结果相同。
//例如：(26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2 
// 
// 修正
//a.c++ 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上⼀个负号」。
//例如： - 1 % 3 = -(1 % 3) = -1
//b.因为有负数，为了防⽌发⽣「出现负数」的结果，以(a % n + n) % n 的形式输出保证为正。
//例如： - 1 % 3 = (-1 % 3 + 3) % 3 = 2

//设 i 为数组中的任意位置，⽤ sum[i] 表⽰[0, i] 区间内所有元素的和。
//• 想知道有多少个「以 i 为结尾的可被 k 整除的⼦数组」，就要找到有多少个起始位置为 x1,x2, x3... 
// 使得[x, i] 区间内的所有元素的和可被 k 整除。
//• 设[0, x - 1] 区间内所有元素之和等于 a ，[0, i] 区间内所有元素的和等于 b ，可得(b - a) % k == 0 。
//• 由同余定理可得，[0, x - 1] 区间与[0, i] 区间内的前缀和同余。于是问题就变成：
//找到在[0, i - 1] 区间内，有多少前缀和的余数等于 sum[i] % k 的即可。
//我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，有多少个前缀和等于sum[i] - k 。
//因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for (auto x : nums)
        {
            sum += x;
            int r = (sum % k + k) % k;
            if (hash.count(r))ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};


// 连续数组

//稍微转化⼀下题⽬，就会变成我们熟悉的题：
//• 本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。
//• 如果将 0 记为 - 1 ， 1 记为 1 ，问题就变成了找出⼀段区间，这段区间的和等于 0 。
//• 于是，就和 560. 和为 K 的⼦数组 这道题的思路⼀样
//设 i 为数组中的任意位置，⽤ sum[i] 表⽰[0, i] 区间内所有元素的和。
//想知道最⼤的「以 i 为结尾的和为 0 的⼦数组」，就要找到从左往右第⼀个 x1 使得[x1, i]区间内的所有元素的和为 0 。
//那么[0, x1 - 1] 区间内的和是不是就是 sum[i] 了。
//于是问题就变成：
//• 找到在[0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可。
//我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，第⼀个前缀和等于 sum[i]的位置。
//因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边记录第⼀次出现该前缀和的位置。

class Solution {
public:
    int findMaxLength(vector<int>& nums)
    {
        int n = nums.size();
        unordered_map<int, int> hash;//前缀和，下标
        hash[0] = -1;
        int sum = 0, ret = 0;
        for (int i = 0; i < n; i++)
        {
            sum += (nums[i] == 0 ? -1 : 1);
            if (hash.count(sum))ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};


//矩阵区域和

//⼆维前缀和的简单应⽤题，关键就是我们在填写结果矩阵的时候，
//要找到原矩阵对应区域的「左上⻆」以及「右下⻆」的坐标（推荐⼤家画图）
//左上⻆坐标： x1 = i - k，y1 = j - k ，但是由于会「超过矩阵」的范围，因此需要对 0 取⼀个 max 。
//因此修正后的坐标为： x1 = max(0, i - k), y1 = max(0, j - k);
//
//右下⻆坐标： x1 = i + k，y1 = j + k ，但是由于会「超过矩阵」的范围，因此需要对 m- 1 ，以及 n - 1 取⼀个 min 。
//因此修正后的坐标为： x2 = min(m - 1, i + k),y2 = min(n - 1, j + k) 。
//
//然后将求出来的坐标代⼊到「⼆维前缀和矩阵」的计算公式上即可~（但是要注意下标的映射关系）

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
    {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        vector<vector<int>> answer(m, vector<int>(n));

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                int bx = max(i - k, 1);
                int by = max(j - k, 1);
                int ex = min(m, i + k);
                int ey = min(n, j + k);
                answer[i - 1][j - 1] = dp[ex][ey] - dp[bx - 1][ey] - dp[ex][by - 1] + dp[bx - 1][by - 1];
            }
        }
        return answer;
    }
};

//-------------------------------------------------------------------位运算----------------------------------------------------


// 判断字符是否唯⼀

//利⽤「位图」的思想，每⼀个「⽐特位」代表⼀个「字符，⼀个 int 类型的变量的 32 位⾜够表⽰所有的⼩写字⺟。
//⽐特位⾥⾯如果是 0 ，表⽰这个字符没有出现过。
//⽐特位⾥⾯的值是 1 ，表⽰该字符出现过。
//那么我们就可以⽤⼀个「整数」来充当「哈希表」

class Solution
{
public:
    bool isUnique(string astr)
    {
        if (astr.size() > 26)
        {
            return false;
        }
        int bitmap = 0;
        for (auto ch : astr)
        {
            int i = ch - 'a';
            if (((bitmap >> i) & 1) == 1)return false;
            else bitmap |= (1 << i);
        }
        return true;
    }
};


//丢失的数字

//如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在⼀起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数~

class Solution {
public:
    int missingNumber(vector<int>& nums)
    {
        int x = 0;
        for (auto n : nums)
        {
            x ^= n;
        }
        for (int i = 0; i <= nums.size(); i++)
        {
            x ^= i;
        }
        return x;
    }
};


//两整数之和

//◦ 异或^ 运算本质是「⽆进位加法」；
//◦ 按位与& 操作能够得到「进位」；
//◦ 然后⼀直循环进⾏，直到「进位」变成 0 为⽌。


class Solution {
public:
    int getSum(int a, int b)
    {
        while (b != 0)
        {
            int x = a ^ b;
            int y = (a & b) << 1;
            a = x;
            b = y;
        }
        return a;
    }
};


//只出现⼀次的数字 II

//由于整个数组中，需要找的元素只出现了「⼀次」，其余的数都出现的「三次」，
//因此我们可以根据所有数的「某⼀个⽐特位」的总和 % 3 的结果，快速定位到 ret 的「⼀个⽐特位上」的值是0 还是 1 。
//这样，我们通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来。

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (auto x : nums)
            {

                if (((x >> i) & 1) == 1)
                {
                    sum++;
                }

            }
            sum %= 3;//统计完nums中所有数的第i位才模3
            if (sum == 1)
            {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};


//只出现一次的数字Ⅲ

//思路

//先把数组中的数字全部异或起来
//得到了a^b
//接下来我们的思路是把a、b分开
//先找到a^b最低位为1的位置记为m
//分别将数组中的每个数右移m位
//根据与1、与0 相与的结果分为两组
//再分别与数组中的数异或 （相同的数两两异或为0）
//就可以得到分别得到a、b


class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        int a = 0, b = 0, x = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            x ^= nums[i];
        }
        int m = 0;
        while (1)
        {
            if (((x >> m) & 1) == 1)
            {
                break;
            }
            else
            {
                m++;
            }
        }
        for (auto n : nums)
        {
            if (((n >> m) & 1) == 1)
            {
                a ^= n;
            }
            else
            {
                b ^= n;
            }
        }
        return { a,b };
    }
};

//消失的两个数字

//先将数组中的数和[1, n + 2] 区间内的所有数「异或」在⼀起，问题就变成了：
//有两个数出现了「⼀次」，其余所有的数出现了「两次」。
//进⽽变成了 260. 只出现⼀次的数字 III 这道题。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        for (auto num : nums)
        {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            ret ^= i;
        }
        int x = 0;
        while (1)
        {
            if (((ret >> x) & 1) == 1)
            {
                break;
            }
            else
            {
                x++;
            }
        }
        int a = 0, b = 0;
        for (auto n : nums)
        {
            if (((n >> x) & 1) == 1)
            {
                b ^= n;
            }
            else
                a ^= n;
        }
        for (int i = 1; i <= nums.size() + 2; i++)
        {
            if (((i >> x) & 1) == 1)
            {
                b ^= i;
            }
            else
                a ^= i;
        }
        return { a,b };
    }
};


//-------------------------------------------------模拟-----------------------------------------------------------------

// 替换所有的问号

//纯模拟。
//从前往后遍历整个字符串，找到问号之后，就⽤ a ~z 的每⼀个字符去尝试替换即可。

class Solution {
public:
    string modifyString(string s)
    {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
            {
                for (char ch = 'a'; ch <= 'z'; ch++)
                {
                    if ((i == 0 || s[i - 1] != ch) && (i == n - 1 || s[i + 1] != ch))
                    {
                        s[i] = ch;
                    }
                }
            }
        }
        return s;
    }
};


//提莫攻击

//模拟 + 分情况讨论。
//计算相邻两个时间点的差值：
//i.如果差值⼤于等于中毒时间，说明上次中毒可以持续 duration 秒；
//ii.如果差值⼩于中毒时间，那么上次的中毒只能持续两者的差值。

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration)
    {
        int ret = 0;
        int n = timeSeries.size();
        for (int i = 1; i < n; i++)
        {
            int x = timeSeries[i] - timeSeries[i - 1];
            if (x >= duration)
            {
                ret += duration;
            }
            else
            {
                ret += x;
            }
        }
        return ret + duration;
    }
};


//N 字形变换

//找规律，⽤ row 代替⾏数，row = 4 时画出的 N 字形如下：
//0                  2row - 2                    4row - 4
//1         2row - 3 2row - 1           4row - 5 4row - 3
//2 2row - 4         2row     4row - 6           4row - 2
//3                  2row + 1                    4row - 1
//不难发现，数据是以 2row - 2 为⼀个周期进⾏规律变换的。将所有数替换成⽤周期来表⽰的变量：
//第⼀⾏的数是：0, 2row - 2, 4row - 4；
//第⼆⾏的数是：1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1；
//第三⾏的数是：2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2；
//第四⾏的数是：3, (2row - 2) + 3, (4row - 4) + 3。
//可以观察到，第⼀⾏、第四⾏为差为 2row - 2 的等差数列；第⼆⾏、第三⾏除了第⼀个数取值为⾏
//数，每组下标为(2n - 1, 2n)的数围绕（2row - 2）的倍数左右取值。
//以此规律，我们可以写出迭代算法。

class Solution {
public:
    string convert(string s, int numRows)
    {
        int n = s.size();
        if (numRows == 1)return s;
        //细节！如果没有这个判断就会超出时间限制！
        //d就会=0 i+0就会一直是i<n 死循环！
        int d = 2 * numRows - 2;//找规律 -> 公差
        string ret;
        for (int i = 0; i < n; i += d)//排序后的第0行
        {
            ret += s[i];
        }
        //1~n-2行
        //k不可以写成k<=numRows-2
        //因为numRows=2时,k=0就会导致第二行没有加入到结果中
        for (int k = 1; k < numRows - 1; k++)
        {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
            {
                if (i < n)ret += s[i];
                if (j < n)ret += s[j];
            }
        }
        //最后一行
        for (int i = numRows - 1; i < n; i += d)
        {
            ret += s[i];
        }
        return ret;
    }
};


//外观数列

class Solution {
public:
    string countAndSay(int n)
    {
        string s = "1";
        for (int i = 1; i < n; i++)//只需要解释n-1次 因为第一次是1
        {
            string tmp;
            for (int l = 0, r = 0; r < s.size();)
            {
                while (r < s.size() && s[l] == s[r])
                {
                    r++;
                }
                tmp += to_string(r - l) + s[l];
                l = r;
            }
            s = tmp;
        }
        return s;
    }
};


// 数⻘蛙

//当遇到 'r' 'o' 'a' 'k' 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，
//有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；
//如果没有，直接返回 - 1 ；
//当遇到 'c' 这个字符的时候，我们去看看 'k' 这个字符有没有⻘蛙叫出来。
//如果有，就让这个⻘蛙继续去喊 'c' 这个字符；
//如果没有的话，就重新搞⼀个⻘蛙。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs)
    {
        string t = "croak";
        int n = t.size();
        vector<int> ret(n);//数组模拟哈希表
        unordered_map<char, int> index;//字符，对应的下标
        for (int i = 0; i < n; i++)
        {
            index[t[i]] = i;//将字符和相应的下标对应
        }
        for (auto ch : croakOfFrogs)
        {
            if (ch == 'c')
            {
                if (ret[index['k']] != 0)ret[index['k']]--;
                //如果最后一个字符有值，就表示已经有蛙叫到了结尾，所以可以开始新一轮叫了
                ret[index[ch]]++;
            }
            else
            {
                //每遍历到一个字符，都要判断哈希表中的前一个是否有值，没有直接返回-1
                if (ret[index[ch] - 1] == 0)return -1;
                ret[index[ch] - 1]--;
                ret[index[ch]]++;
            }
        }
        for (int i = 0; i < n - 1; i++)
        {
            if (ret[i] != 0)return -1;
            //数组遍历完了，但是哈希表中除了最后一个字符有值之外，其他也有值也返回-1
        }
        return ret[n - 1];
    }
};



//------------------------------------------------分治 - 快速排序--------------------------------------------------------

//颜⾊分类

//a.初始化 cur = 0，left = -1， right = numsSize ；
//b.当 cur < right 的时候（因为 right 表⽰的是 2 序列的左边界，
//    因此当 cur 碰到right 的时候，说明已经将所有数据扫描完毕了），⼀直进⾏下⾯循环：
//    根据 nums[cur] 的值，可以分为下⾯三种情况：
//        i.nums[cur] == 0 ；说明此时这个位置的元素需要在 left + 1 的位置上，
//        因此交换 left + 1 与 cur 位置的元素，并且让 left++ （指向 0 序列的右边界），
//        cur++ （为什么可以 ++ 呢，是因为 left + 1 位置要么是 0 ，要么是 cur ，交换
//        完毕之后，这个位置的值已经符合我们的要求，因此 cur++ ）；
//        ii.nums[cur] == 1 ；说明这个位置应该在 left 和 cur 之间，此时⽆需交换，直接让 cur++ ，判断下⼀个元素即可；
//        iii.nums[cur] == 2 ；说明这个位置的元素应该在 right - 1 的位置，因此交换right - 1 与 cur 位置的元素，并且让 right-- （指向 2 序列的左边界），
//        cur 不变（因为交换过来的数是没有被判断过的，因此需要在下轮循环中判断）
//c.当循环结束之后：
//        [0, left] 表⽰ 0 序列；
//        [left + 1, right - 1] 表⽰ 1 序列；
//        [right, numsSize - 1] 表⽰ 2 序列。

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        //使用三指针
        //[0,left-1] -> 0
        //[left,i-1] -> 1
        //[i,right-1] -> 待扫描
        //[right,n-1] -> 2
        int n = nums.size();
        int l = -1, i = 0, r = n;
        while (i < r)
        {
            if (nums[i] == 0)
            {
                swap(nums[++l], nums[i++]);
            }
            else if (nums[i] == 1)
            {
                i++;
            }
            else
            {
                swap(nums[--r], nums[i]);
                //！！！注意，这里的i不能++，因为还没有判断（扫描）
            }
        }

    }
};


///快速排序--排序数组

//随机选择基准算法流程：
//函数设计：int randomKey(vector<int>& nums, int left, int right)
//a.在主函数那⾥种⼀颗随机数种⼦；
//b.在随机选择基准函数这⾥⽣成⼀个随机数；
//c.由于我们要随机产⽣⼀个基准，因此可以将随机数转换成随机下标：让随机数% 上区间⼤⼩，
//然后加上区间的左边界即可。
//
//快速排序算法主要流程：
//a.定义递归出⼝；
//b.利⽤随机选择基准函数⽣成⼀个基准元素；
//c.利⽤荷兰国旗思想将数组划分成三个区域；
//d.递归处理左边区域和右边区域。

class Solution
{
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void MergeSort(vector<int>& nums, int l, int r)
    {
        if (l >= r)return;

        //找中间
        int mid = (l + r) >> 1;

        //排序左边右边
        MergeSort(nums, l, mid);
        MergeSort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        //注意边界情况！<= 不是 <
        while (cur1 <= mid && cur2 <= r)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        //其中有一个数组没有结尾
        while (cur1 <= mid)tmp[i++] = nums[cur1++];
        while (cur2 <= r)tmp[i++] = nums[cur2++];

        for (int i = l; i <= r; i++)
        {
            nums[i] = tmp[i - l];
        }

    }
};


//快速选择算法--数组中第k个最大元素

//在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] 
//我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。
//那么我们可以直接去「相应的区间」去寻找最终结果就好了。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        return Qsort(nums, 0, nums.size() - 1, k);
    }
    int Qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r)return nums[l];

        int tmp = nums[rand() % (r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (tmp > nums[i])swap(nums[i++], nums[++left]);
            else if (tmp == nums[i])i++;
            else swap(nums[i], nums[--right]);
        }
        int c = r - right + 1, b = right - left - 1;
        if (c >= k)return Qsort(nums, right, r, k);
        else if (b + c >= k)return tmp;
        else return Qsort(nums, l, left, k - b - c);
    }
};


//最⼩的 k 个数

//在快排中，当我们把数组「分成三块」之后：[l, left][left + 1, right - 1][right, r] ，
//我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出最⼩的 k 个数在哪些区间⾥⾯。
//那么我们可以直接去「相应的区间」继续划分数组即可。

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int cnt)
    {
        srand(time(NULL));
        Qsort(nums, 0, nums.size() - 1, cnt);
        return { nums.begin(),nums.begin() + cnt };
    }
    void Qsort(vector<int>& nums, int l, int r, int cnt)
    {
        if (l >= r)return;
        int tmp = nums[rand() % (r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (tmp > nums[i])swap(nums[i++], nums[++left]);
            else if (tmp == nums[i])i++;
            else swap(nums[i], nums[--right]);
        }
        int a = left - l + 1, b = right - left - 1;
        if (cnt < a) Qsort(nums, l, left, cnt);
        else if (cnt < a + b)return;
        else Qsort(nums, right, r, cnt - a - b);
    }
};


//-------------------------------------------分治 - 归并排序---------------------------------------------------------------

//归并排序-排序数组

//归并排序的流程充分的体现了「分⽽治之」的思想，⼤体过程分为两步：
// 
//◦ 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为 1 ，使整个数组的排序过程被分为
//「左半部分排序」 + 「右半部分排序」；
//◦ 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。

class Solution
{
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        MergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void MergeSort(vector<int>& nums, int l, int r)
    {
        if (l >= r)return;

        //找中间
        int mid = (l + r) >> 1;

        //排序左边右边
        MergeSort(nums, l, mid);
        MergeSort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        //注意边界情况！<= 不是 <
        while (cur1 <= mid && cur2 <= r)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }

        //其中有一个数组没有结尾
        while (cur1 <= mid)tmp[i++] = nums[cur1++];
        while (cur2 <= r)tmp[i++] = nums[cur2++];

        for (int i = l; i <= r; i++)
        {
            nums[i] = tmp[i - l];
        }

    }
};


//数组中的逆序对


class Solution
{
    vector<int> tmp;
public:
    int reversePairs(vector<int>& nums)
    {
        tmp.resize(nums.size());
        return Msort(nums, 0, nums.size() - 1);
    }
    int Msort(vector<int>& nums, int l, int r)
    {
        int ret = 0;
        if (l >= r)return ret;
        int mid = (l + r) >> 1;

        ret += Msort(nums, l, mid);
        ret += Msort(nums, mid + 1, r);
        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] > nums[cur2])
            {
                ret += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
            else
            {
                tmp[i++] = nums[cur1++];
            }
        }
        while (cur1 <= mid)tmp[i++] = nums[cur1++];
        while (cur2 <= r)tmp[i++] = nums[cur2++];
        for (int j = l; j <= r; j++)
        {
            nums[j] = tmp[j - l];
        }
        return ret;
    }
};


//计算右侧小于当前元素的个数

//也是固定一边的值 然后查看另一边的值有多少比这个数大/小

class Solution
{
    vector<int> tmp;
    vector<int> index;
    vector<int> indextmp;
    vector<int> ret;
public:
    vector<int> countSmaller(vector<int>& nums)
    {
        int n = nums.size();
        tmp.resize(n);
        index.resize(n);
        indextmp.resize(n);
        ret.resize(n);
        for (int i = 0; i < n; i++)//数和下标对应 不用哈希表 因为可能会有重复的数字
        {
            index[i] = i;
        }
        Msort(nums, 0, n - 1);
        return ret;
    }

    void Msort(vector<int>& nums, int l, int r)
    {
        if (l >= r)return;
        int mid = (l + r) >> 1;
        Msort(nums, l, mid);
        Msort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= r)
        {
            if (nums[cur1] <= nums[cur2])//降序
            {
                tmp[i] = nums[cur2];
                indextmp[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += (r - cur2 + 1);
                tmp[i] = nums[cur1];
                indextmp[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid)
        {
            tmp[i] = nums[cur1];
            indextmp[i++] = index[cur1++];
        }
        while (cur2 <= r)
        {
            tmp[i] = nums[cur2];
            indextmp[i++] = index[cur2++];
        }
        for (int j = l; j <= r; j++)
        {
            nums[j] = tmp[j - l];
            index[j] = indextmp[j - l];
        }
    }
};


//翻转对

class Solution
{
    vector<int> tmp;
public:
    int reversePairs(vector<int>& nums)
    {
        int n = nums.size();
        tmp.resize(n);
        return Msort(nums, 0, n - 1);
    }

    int Msort(vector<int>& nums, int l, int r)
    {
        if (l >= r)return 0;
        int ret = 0;
        int mid = (l + r) >> 1;
        ret += Msort(nums, l, mid);
        ret += Msort(nums, mid + 1, r);

        int cur1 = l, cur2 = mid + 1, i = 0;
        while (cur1 <= mid)
        {
            while (cur2 <= r && (long long)nums[cur1] <= (long long)nums[cur2] * 2)cur2++;
            ret += (r - cur2 + 1);
            cur1++;
        }
        cur1 = l, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= r)
        {
            tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while (cur1 <= mid)
        {
            tmp[i++] = nums[cur1++];
        }
        while (cur2 <= r)
        {
            tmp[i++] = nums[cur2++];
        }
        for (int j = l; j <= r; j++)
        {
            nums[j] = tmp[j - l];
        }
        return ret;
    }
};



//-----------------------------------------------链表---------------------------------------------------------



// 两数相加

//两个链表都是逆序存储数字的，即两个链表的个位数、十位数等都已经对应，可以直接相加。
//在相加过程中，我们要注意是否产⽣进位，产⽣进位时需要将进位和链表数字⼀同相加。
//如果产⽣进位的位置在链表尾部，即答案位数⽐原链表位数长⼀位，还需要再 new ⼀个结点储存最⾼位。


 struct ListNode 
{
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };
 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        ListNode*cur1=l1,*cur2=l2;
        ListNode*newnode=new ListNode(0);
        ListNode*cur=newnode;
        int t=0;
        while(cur1||cur2||t)//除了判断cur1 cur2 还要判断t t不为0 就证明还要向前进位
        {
            if(cur1)
            {
                t+=cur1->val;
                cur1=cur1->next;
            }
            if(cur2)
            {
                t+=cur2->val;  
                cur2=cur2->next;
            }
            cur->next=new ListNode(t%10);//创建新节点
            cur=cur->next;
            t/=10;
        }
        cur=newnode->next;
        delete newnode;//删除
        return cur;
    }
};


//两两交换链表中的节点

//画图即可完成。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)return head;
        ListNode* newnode = new ListNode();
        newnode->next = head;
        ListNode* prev = newnode;
        ListNode* cur = prev->next;
        ListNode* next = head->next;
        ListNode* nnext = head->next->next;
        while (cur && next)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if (cur)next = cur->next;//判断cur是否为空 防止空指针
            if (next)nnext = next->next;
        }
        cur = newnode->next;
        delete newnode;
        return cur;
    }
};


//重排链表

//1. 找中间节点；
//2. 中间部分往后的逆序；
//3. 合并两个链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr)return;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* cur = slow->next;
        slow->next = nullptr;//断开
        ListNode* newhead = new ListNode(0);
        ListNode* h = newhead;
        ListNode* prev = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            h->next = cur;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        ListNode* cur1 = head, * cur2 = newhead->next;
        while (cur1 && cur2)
        {
            ListNode* n1 = cur1->next;
            ListNode* n2 = cur2->next;
            cur1->next = cur2;
            cur2->next = n1;
            cur1 = n1;
            cur2 = n2;
        }
    }
};


//合并 K 个升序链表


//方法1:利用小根堆
//我们可以把所有的头结点放进⼀个⼩根堆中，这样就能快速的找到每次 K 个链表中，最小的元素是哪个

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;//向下调整，所以谁大谁去
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        //创建小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        //让所有的头节点进入小根堆
        for (auto l : lists)
        {
            if (l)heap.push(l);
        }

        //合并k个链表
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        while (!heap.empty())
        {
            prev->next = heap.top();
            heap.pop();
            prev = prev->next;

            if (prev->next)
            {
                heap.push(prev->next);
            }
        }

        prev = newhead->next;
        delete newhead;
        return prev;
    }
};

//方法2：分治
// 
//1. 特判，如果题⽬给出空链表，无需合并，直接返回；
//2. 返回递归结果。
//递归函数设计：
//1. 递归出口：如果当前要合并的链表编号范围左右值相等，⽆需合并，直接返回当前链表；
//2. 应⽤二分思想，等额划分左右两段需要合并的链表，使这两段合并后的⻓度尽可能相等；
//3. 对左右两段分别递归，合并[l, r]范围内的链表；
//4. 再调⽤ mergeTwoLists 函数进⾏合并（就是合并两个有序链表）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return Msort(lists, 0, lists.size() - 1);
    }

    ListNode* Msort(vector<ListNode*>& lists, int l, int r)
    {
        if (l > r)return nullptr;
        if (l == r)return lists[l];

        int mid = (l + r) >> 1;

        ListNode* l1 = Msort(lists, l, mid);
        ListNode* l2 = Msort(lists, mid + 1, r);

        //合并一左一右
        return Toget(l1, l2);
    }

    ListNode* Toget(ListNode* l1, ListNode* l2)
    {
        if (l1 == nullptr)return l2;
        if (l2 == nullptr)return l1;

        ListNode head;
        ListNode* cur1 = l1, * cur2 = l2, * prev = &head;
        //初始化head
        head.next = nullptr;

        while (cur1 && cur2)
        {
            if (cur1->val <= cur2->val)
            {
                prev->next = cur1;
                prev = cur1;
                cur1 = cur1->next;
            }
            else
            {
                prev->next = cur2;
                prev = cur2;
                cur2 = cur2->next;
            }
        }

        while (cur1)
        {
            prev->next = cur1;
            prev = cur1;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            prev->next = cur2;
            prev = cur2;
            cur2 = cur2->next;
        }
        return head.next;
    }
};


//K个⼀组翻转链表

//先求出⼀共需要逆序多少组（假设逆序 n 组），然后重复 n 次⻓度为 k 的链表的逆序（头插）即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        ListNode* cur = head;
        int len = 0;
        while (cur)
        {
            cur = cur->next;
            len++;
        }
        int n = len / k;
        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        cur = head;
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                if (cur)
                {

                    ListNode* next = cur->next;
                    cur->next = prev->next;
                    prev->next = cur;
                    cur = next;
                }
            }
            prev = tmp;
        }
        prev->next = cur;
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};



//----------------------------------------------哈希表-------------------------------------------------------

//两数之和

//如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中，
//然后直接在哈希表中查找每⼀个元素的 target - nums[i] ，就能快速的找到「目标和的下标」。
//• 这⾥有一个⼩技巧，我们可以不⽤将元素全部放入到哈希表之后，再来⼆次遍历（因为要处理元素相同的情况）。
// ⽽是在将元素放入到哈希表中的「同时」，直接来检查表中是否已经存在当前元素所对应的⽬标元素（即 target - nums[i]）。
// 如果它存在，那我们已经找到了对应解，并⽴即将其返回。⽆需将元素全部放入哈希表中，提⾼效率。
//• 因为哈希表中查找元素的时间复杂度是 O(1) ，遍历⼀遍数组的时间复杂度为 O(N) ，因此可以将时间复杂度降到 O(N) 。
//这是⼀个典型的「用空间交换时间」的⽅式。

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int, int> hash;//<num[i],i>
        for (int i = 0; i < nums.size(); i++)
        {
            int x = target - nums[i];
            if (hash.count(x))
            {
                return { hash[x],i };
            }
            hash[nums[i]] = i;
        }
        return { -1,-1 };
    }
};


//判断是否互为字符重排

//1. 当两个字符串的⻓度不相等的时候，是不可能构成互相重排的，直接返回 false ；
//2. 如果两个字符串能够构成互相重排，那么每个字符串中「各个字符」出现的「次数」⼀定是相同的。
//因此，我们可以分别统计出这两个字符串中各个字符出现的次数，然后逐个⽐较是否相等即可。
//这样的话，我们就可以选择「哈希表」来统计字符串中字符出现的次数。

class Solution {
public:
    bool CheckPermutation(string s1, string s2)
    {
        if (s1.size() != s2.size())return false;
        int hash[26] = { 0 };
        for (auto s : s1)
        {
            hash[s - 'a']++;
        }
        for (auto s : s2)
        {
            hash[s - 'a']--;
        }
        for (int i = 0; i < 26; i++)
        {
            if (hash[i] != 0)
            {
                return false;
            }
        }
        return true;
    }
};


//58. 存在重复元素 I

//方法一:
//用哈希表记录数组的值和该数字出现的次数
//如果次数大于1，就返回true

class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_map<int, int> hash;//数组，次数
        for (auto x : nums)
        {
            hash[x]++;
            if (hash[x] > 1)
            {
                return true;
            }
        }
        return false;
    }
};

//方法二:
//
//遍历数组，如果哈希表中已经有这个值了，那么返回true
//没有就插入

class Solution {
public:
    bool containsDuplicate(vector<int>& nums)
    {
        unordered_set<int> hash;
        for (auto x : nums)
        {
            if (hash.count(x))return true;
            else hash.insert(x);
        }
        return false;
    }
};


//59. 存在重复元素 II

//解决该问题需要我们快速定位到两个信息：
//• 两个相同的元素；
//• 这两个相同元素的下标。
//因此，我们可以使用「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，
//将「数组元素」和「下标」绑定在⼀起，存入到「哈希表」中。

class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;//<num[i],i>
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i]))
            {
                if (i - hash[nums[i]] <= k)return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};


//60. 字母异位词分组

//互为字⺟异位词的单词有⼀个特点：
//将它们「排序」之后，两个单词应该是「完全相同」的。
//所以，我们可以利⽤这个特性，将单词按照字典序排序，
//如果排序后的单词相同的话，就划分到同⼀组中。
//这时我们就要处理两个问题：
//• 排序后的单词与原单词需要能互相映射；
//• 将排序后相同的单词，「划分到同⼀组」；

class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs)
    {
        unordered_map<string, vector<string>> hash;
        for (auto s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }

        vector<vector<string>> ret;
        for (const auto &xy : hash)
        {
            ret.push_back(xy.second);
        }
        return ret;
    }
};


//---------------------------------------------字符串----------------------------------------------------------

//61. 最长公共前缀

//我们可以先找出前两个的最⻓公共前缀，
//然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较，
//这样就可以找出所有字符串的最⻓公共前缀

class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        // 我们可以先找出前两个的最⻓公共前缀
        // 然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较
        // 这样就可以找出所有字符串的最⻓公共前缀

        string ret = strs[0];
        for (int i = 1; i < strs.size(); i++)
        {
            ret = FindCom(ret, strs[i]);
        }
        return ret;
    }

    string FindCom(string s1, string s2)
    {
        int i = 0;
        while (i < min(s1.size(), s2.size()) && s1[i] == s2[i])i++;
        return s1.substr(0, i);
    }
};


//62. 最长回文子串

//中心扩散思想

class Solution {
public:
    string longestPalindrome(string s)
    {
        //使用中心扩展算法
        int begin = 0, len = 1;
        int n = s.size();
        //枚举每一个中点

        for (int i = 0; i < n; i++)
        {
            //奇数
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r])
            {
                l--; r++;
            }
            if (r - l - 1 > len)//应该是r-l-1 因为 r/l这两个临界点不算 已经超出了范围
            {
                len = r - l - 1;
                begin = l + 1;//因为l可能是-1 但是s下标最小是0
            }
        }
        for (int i = 0; i < n; i++)
        {
            //偶数
            int l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r])
            {
                l--; r++;
            }
            if (r - l - 1 > len)
            {
                len = r - l - 1;
                begin = l + 1;
            }
        }
        return s.substr(begin, len);
    }
};



//63. ⼆进制求和

class Solution
{
public:
    string addBinary(string a, string b)
    {
        int x = a.size() - 1, y = b.size() - 1, t = 0;
        string ret;
        while (x >= 0 || y >= 0 || t)
        {
            if (x >= 0)t += (a[x--] - '0');
            if (y >= 0)t += (b[y--] - '0');
            ret += (t % 2 + '0');
            t /= 2;
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};


//64. 字符串相乘

//整体思路就是模拟我们小学列竖式计算两个数相乘的过程。但是为了我们书写代码的方便性，
//我们选择⼀种优化版本的，就是在计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去考虑进位。

class Solution
{
public:
    string multiply(string num1, string num2)
    {
        int m = num1.size(), n = num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int> tmp(m + n - 1);
        string ret;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        int t = 0, cur = 0;
        while (cur < m + n - 1 || t)
        {
            if (cur < m + n - 1)t += tmp[cur++];
            ret += (t % 10 + '0');
            t /= 10;
        }
        reverse(ret.begin(), ret.end());

        //记得去前导0
        while (ret.size() > 1 && ret.front() == '0')
        {
            ret.pop_back();
        }

        return ret;
    }
};


//----------------------------------------------------------------------------栈-----------------------------------------------------------------------------

//65. 删除字符中的所有相邻重复项

//直接⽤「数组模拟⼀个栈」结构：在数组的尾部「尾插尾删」，实现栈的「进栈」和「出栈」。那么最后数组存留的内容，就是最后的结果。

class Solution {
public:
    string removeDuplicates(string s)
    {
        string ret;
        for (char ch : s)
        {
            if (ret.size() && ret.back() == ch)
            {
                ret.pop_back();
            }
            else
            {
                ret += ch;
            }
        }
        return ret;
    }
};


//66. 比较含退格的字符串

//由于退格的时候需要知道「前面元素」的信息，⽽且退格也符合「后进先出」的特性。
//因此我们可以使⽤「栈」结构来模拟退格的过程。
//• 当遇到非 # 字符的时候，直接进栈；
//• 当遇到 # 的时候，栈顶元素出栈。
//为了⽅便统计结果，我们使⽤「数组」来模拟实现栈结构

class Solution {
public:
    bool backspaceCompare(string s, string t)
    {
        string s1, s2;
        for (auto ch : s)
        {
            if (ch == '#')
            {
                if (s1.size())
                    s1.pop_back();
            }
            else
            {
                s1 += ch;
            }
        }
        for (auto ch : t)
        {
            if (ch == '#')
            {
                if (s2.size())
                    s2.pop_back();
            }
            else
            {
                s2 += ch;
            }
        }
        return s1 == s2;
    }
};


//67. 基本计算器 II

//• 当⼀个数前⾯是 '+' 号的时候，这⼀个数是否会被⽴即计算是「不确定」的，因此我们可以先压入栈中；
//• 当⼀个数前⾯是 '-' 号的时候，这⼀个数是否被⽴即计算也是「不确定」的，但是这个数已经和前面的 - 号绑定了，因此我们可以将这个数的相反数压入栈中；
//• 当⼀个数前⾯是 '*' 号的时候，这⼀个数可以⽴即与前⾯的⼀个数相乘，此时我们让将栈顶的元素乘上这个数；
//• 当⼀个数前⾯是 '/' 号的时候，这⼀个数也是可以⽴即被计算的，因此我们让栈顶元素除以这个数。

class Solution
{
public:
    int calculate(string s)
    {
        vector<int> st;
        int i = 0, n = s.size();
        char op = '+';

        while (i < n)
        {
            if (s[i] == ' ')i++;//跳过空格
            else if (s[i] >= '0' && s[i] <= '9')
            {
                int num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')//可能是多位数
                {
                    num = num * 10 + (s[i++] - '0');//把数字提取出来
                }
                if (op == '+')st.push_back(num);
                else if (op == '-')st.push_back(-num);
                else if (op == '*')st.back() *= num;//更新栈顶的值
                else st.back() /= num;//更新栈顶的值
            }
            else//是符号
            {
                op = s[i++];
            }
        }
        int ret = 0;
        for (auto nn : st)
        {
            ret += nn;
        }
        return ret;
    }
};


//68. 字符串解码

//对于 3[ab2[cd]] ，我们需要先解码内部的，再解码外部：
//• 3[ab2[cd]] -> 3[abcd cd]->abcdcd abcdcd abcdcd
//在解码 cd 的时候，我们需要保存 3 ab 2 这些元素的信息，并且这些信息使⽤的顺序是从后往前，正好符合栈的结构，因此我们可以定义两个栈结构，
//⼀个⽤来保存解码前的重复次数 k （左括号前的数字），
//⼀个⽤来保存解码之前字符串的信息（左括号前的字符串信息）。

class Solution
{
public:
    string decodeString(string s)
    {
        stack<int> nums;
        stack<string> st;
        st.push("");//初始化 不然pop/top会崩溃
        int i = 0;
        int n = s.size();
        while (i < n)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                int num = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9')
                {
                    num = num * 10 + (s[i++] - '0');
                }
                nums.push(num);
            }
            else if (s[i] == '[')
            {
                i++;
                //把括号后面的字符串提出
                string tmp;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st.push(tmp);
            }
            else if (s[i] == ']')
            {
                string op = st.top();
                st.pop();
                int nn = nums.top();
                nums.pop();

                while (nn--)
                {
                    st.top() += op;
                }
                i++;//跳过右括号
            }
            else
            {
                string ss;
                while (i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    ss += s[i++];
                }
                st.top() += ss;
            }
        }
        return st.top();
    }
};


//69. 验证栈序列

//⼀直让元素进栈，进栈的同时判断是否需要出栈。
//当所有元素模拟完毕之后，如果栈中还有元素，那么就是⼀个非法的序列。
//否则，就是⼀个合法的序列

class Solution
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
    {
        stack<int> st;
        int i = 0, n = popped.size();
        for (auto x : pushed)
        {
            st.push(x);
            while (!st.empty() && i < n && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }
        return i == n;
    }
};


//-----------------------------------------------------------队列 + 宽搜（BFS）--------------------------------------------------------------------------------------


//70. N 叉树的层序遍历

//层序遍历即可~
//仅需多加⼀个变量，⽤来记录每⼀层结点的个数就好了。


// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        vector<vector<int>> ret;
        queue<Node*> q;
        if (root == nullptr)return ret;
        q.push(root);
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for (auto child : t->children)
                {
                    if (child != nullptr)q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};


//71. ⼆叉树的锯⻮形层序遍历

//在正常的层序遍历过程中，我们是可以把⼀层的结点放在⼀个数组中去的。
//既然我们有这个数组，在合适的层数逆序就可以得到锯⻮形层序遍历的结果。


 //Definition for a binary tree node.
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
        vector<vector<int>> ret;
        queue<TreeNode*>q;
        if (root == nullptr)return ret;
        q.push(root);
        int level = 1;
        while (q.size())
        {
            int sz = q.size();
            vector<int> tmp;
            for (int i = 0; i < sz; i++)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if (t->left)q.push(t->left);
                if (t->right)q.push(t->right);
            }
            //先判断再++
            if (level % 2 == 0)
            {
                reverse(tmp.begin(), tmp.end());
            }
            level++;
            ret.push_back(tmp);
        }
        return ret;
    }
};


//72. ⼆叉树的最⼤宽度

 // Definition for a binary tree node.
 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
 TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root)
    {
        //用数组代替队列
        //记录节点和下标
        vector<pair<TreeNode*, unsigned int>> q;
        unsigned int ret = 0;
        if (root == nullptr)return ret;
        q.push_back({ root,1 });

        while (q.size())
        {
            auto [x1, y1] = q[0];//队列第一个结点
            auto [x2, y2] = q.back();//队列最后一个结点
            ret = max(ret, y2 - y1 + 1);

            vector<pair<TreeNode*, unsigned int>> tmp;
            for (auto [x, y] : q)
            {
                if (x->left)tmp.push_back({ x->left,2 * y });
                if (x->right)tmp.push_back({ x->right,2 * y + 1 });
            }
            q = tmp;//更新下一层
        }
        return ret;
    }
};


//73. 在每个树⾏中找最⼤值


 //Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
 
class Solution {
public:
    vector<int> largestValues(TreeNode* root)
    {
        vector<int> ret;
        queue<TreeNode*> q;
        if (root == nullptr)return ret;
        q.push(root);

        while (q.size())
        {
            int tmp = INT_MIN;
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                TreeNode* t = q.front();
                q.pop();
                tmp = max(tmp, t->val);

                if (t->left)q.push(t->left);
                if (t->right)q.push(t->right);
            }
            ret.push_back(tmp);
            tmp = INT_MIN;
        }
        return ret;
    }
};


//------------------------------------------------------- 优先级队列（堆）-----------------------------------------------------------------

//74. 最后⼀块石头的重量

//• 我们可以创建⼀个⼤根堆；
//• 然后将所有的⽯头放⼊⼤根堆中；
//• 每次拿出前两个堆顶元素粉碎⼀下，如果还有剩余，就将剩余的⽯头继续放⼊堆中；
//这样就能快速的模拟出这个过程。


class Solution {
public:
    int lastStoneWeight(vector<int>& stones)
    {
        priority_queue<int> pq;
        for (auto x : stones)
        {
            pq.push(x);
        }
        while (pq.size() > 1)
        {
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            if (a > b)pq.push(a - b);
            else pq.push(b - a);
        }
        return pq.top();
    }
};


//75. 数据流中的第 K 大元素

class KthLargest
{
    priority_queue<int, vector<int>, greater<int>> q;
    int kk;
public:
    KthLargest(int k, vector<int>& nums)
    {
        kk = k;
        for (auto x : nums)
        {
            q.push(x);
        }
        while (q.size() > kk)
        {
            q.pop();
        }
    }

    int add(int val)
    {
        q.push(val);
        while (q.size() > kk)
        {
            q.pop();
        }
        return q.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */


//76. 前 K 个⾼频单词

//算法思路：
//• 稍微处理⼀下原数组：
//a.我们需要知道每⼀个单词出现的频次，因此可以先使⽤哈希表，统计出每⼀个单词出现的频次；
//b.然后在哈希表中，选出前 k ⼤的单词
// （为什么不在原数组中选呢？因为原数组中存在重复的单词，哈希表⾥⾯没有重复单词，并且还有每⼀个单词出现的频次）
// 
//• 如何使⽤堆，拿出前 k ⼤元素：
//a.先定义⼀个⾃定义排序，我们需要的是前 k ⼤，因此需要⼀个⼩根堆。但是当两个字符串的
//频次相同的时候，我们需要的是字典序较⼩的，此时是⼀个⼤根堆的属性，在定义⽐较器的时候需要注意！
//▪ 当两个字符串出现的频次不同的时候：需要的是基于频次⽐较的⼩根堆
//▪ 当两个字符串出现的频次相同的时候：需要的是基于字典序⽐较的⼤根堆
//b.定义好⽐较器之后，依次将哈希表中的字符串插⼊到堆中，维持堆中的元素不超过 k 个；
//c.遍历完整个哈希表后，堆中的剩余元素就是前 k ⼤的元素

class Solution
{
    typedef pair<string, int> psi;
    struct cmp
    {
        bool operator()(psi s1, psi s2)
        {
            if (s1.second == s2.second)
            {
                return s1.first < s2.first;
            }
            return s1.second > s2.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        vector<string> ret;
        priority_queue<psi, vector<psi>, cmp> pq;
        unordered_map<string, int> hash;
        for (auto s : words)
        {
            hash[s]++;
        }

        for (auto ppsi : hash)
        {
            pq.push({ ppsi });
            if (pq.size() > k)pq.pop();
        }

        for (int i = 0; i < k; i++)
        {
            ret.push_back(pq.top().first);
            pq.pop();
        }
        reverse(ret.begin(), ret.end());

        return ret;

    }
};

//77. 数据流的中位数

class MedianFinder
{
    priority_queue<int> left;//大根堆
    priority_queue<int, vector<int>, greater<int>> right;//小根堆
public:
    MedianFinder()
    {}

    void addNum(int num)
    {
        if (left.size() == right.size())
        {
            if (left.empty() || num <= left.top())
            {
                left.push(num);
            }
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else//m==n+1
        {
            if (num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else
            {
                right.push(num);
            }
        }
    }

    double findMedian()
    {
        if (left.size() == right.size())return (left.top() + right.top()) / 2.0;
        else return left.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */


//-------------------------------------------------------BFS 解决 FloodFill 算法---------------------------------------------------------

//78. 图像渲染

//可以利⽤「深搜」或者「宽搜」，遍历到与该点相连的所有「像素相同的点」，然后将其修改成指定的像素即可。

class Solution
{
    typedef pair<int, int> pii;
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int prev = image[sr][sc];
        if (prev == color)return image;

        int m = image.size(), n = image[0].size();

        queue<pii> q;
        q.push({ sr,sc });

        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            image[a][b] = color;

            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && prev == image[x][y])
                {
                    q.push({ x,y });
                }
            }
        }
        return image;
    }
};


//79. 岛屿数量

//遍历整个矩阵，每次找到「⼀块陆地」的时候：
//• 说明找到「⼀个岛屿」，记录到最终结果 ret ⾥⾯；
//• 并且将这个陆地相连的所有陆地，也就是这块「岛屿」，全部「变成海洋」。这样的话，我们下次
//遍历到这块岛屿的时候，它「已经是海洋」了，不会影响最终结果。
//• 其中「变成海洋」的操作，可以利⽤「深搜」和「宽搜」解决，其实就是 733. 图像渲染 这道题~
//这样，当我们，遍历完全部的矩阵的时候， ret 存的就是最终结果

class Solution
{
    typedef pair<int, int> pii;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[301][301];
    int m = 0, n = 0;
public:
    int numIslands(vector<vector<char>>& grid)
    {
        int ret = 0;
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && vis[i][j] == false)
                {
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }
        return ret;
    }

    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pii> q;
        q.push({ i,j });
        vis[i][j] = true;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] == '1')
                {
                    q.push({ x,y });
                    vis[x][y] = true;
                }
            }
        }
    }
};


//80. 岛屿的最⼤⾯积

//遍历整个矩阵，每当遇到⼀块⼟地的时候，就⽤「深搜」或者「宽搜」将与这块⼟地相连的「整个岛屿」的⾯积计算出来。
//• 然后在搜索得到的「所有的岛屿⾯积」求⼀个「最⼤值」即可。
//• 在搜索过程中，为了「防⽌搜到重复的⼟地」：
//◦ 可以开⼀个同等规模的「布尔数组」，标记⼀下这个位置是否已经被访问过；
//◦ 也可以将原始矩阵的 1 修改成 0 ，但是这样操作会修改原始矩阵。

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[51][51];
    int ret = INT_MIN;
    typedef pair<int, int> pii;
    int m = 0, n = 0;
public:
    int maxAreaOfIsland(vector<vector<int>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && vis[i][j] == 0)
                {
                    ret = max(bfs(grid, i, j), ret);
                }
            }
        }
        return ret == INT_MIN ? 0 : ret;
    }

    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        queue<pii> q;
        q.push({ i,j });
        vis[i][j] = true;
        int count = 1;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] == 1)
                {
                    count++;
                    q.push({ x,y });
                    vis[x][y] = true;
                }
            }
        }
        return count;
    }
};


//81. 被围绕的区域

//正难则反。
//可以先利⽤ bfs 将与边缘相连的 '0' 区域改成‘*’，然后重新遍历矩阵，将'0'修改成 'X' 即可。

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int m = 0, n = 0;
public:
    void solve(vector<vector<char>>& board)
    {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++)
        {
            if (board[i][0] == 'O')
            {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O')
            {
                bfs(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++)
        {
            if (board[0][j] == 'O')
            {
                bfs(board, 0, j);
            }
            if (board[m - 1][j] == 'O')
            {
                bfs(board, m - 1, j);
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == '*')
                {
                    board[i][j] = 'O';
                }
            }
        }
    }

    void bfs(vector<vector<char>>& board, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({ i,j });
        board[i][j] = '*';
        while (q.size())
        {
            auto [a, b] = q.front(); q.pop();

            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                {
                    board[x][y] = '*';
                    q.push({ x,y });

                }
            }
        }

    }
};


//--------------------------------------------------------BFS 解决最短路问题------------------------------------------------------------


//82. 迷宫中离入口最近的出口

//利⽤层序遍历来解决迷宫问题，是最经典的做法。
//我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离

class Solution
{
    typedef pair<int, int> pii;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[101][101];
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance)
    {
        queue<pii> q;
        q.push({ entrance[0],entrance[1] });
        vis[entrance[0]][entrance[1]] = true;
        int step = 0;
        int m = maze.size(), n = maze[0].size();

        while (q.size())
        {
            step++;
            int sz = q.size();
            for (int i = 0; i < sz; i++)
            {
                auto [a, b] = q.front(); q.pop();
                for (int j = 0; j < 4; j++)
                {
                    int x = a + dx[j], y = b + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && vis[x][y] == false)
                    {
                        if (x == m - 1 || x == 0 || y == 0 || y == n - 1)
                        {
                            return step;
                        }
                        q.push({ x,y });
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};



//83. 最⼩基因变化

//如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为 1的最短路问题」。
//因此，从起始的字符串开始，来⼀次 bfs 即可。

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank)
    {
        unordered_set<string> hash;
        for (auto s : bank)
        {
            hash.insert(s);
        }
        unordered_set<string> vis;
        string t = "ACGT";
        int count = 0;

        queue<string> q;

        q.push(startGene);
        vis.insert(startGene);

        while (q.size())
        {
            count++;
            int sz = q.size();
            for (int j = 0; j < sz; j++)
            {
                auto tmp = q.front(); q.pop();
                for (int i = 0; i < startGene.size(); i++)
                {
                    string str = tmp;
                    for (auto ch : t)
                    {
                        str[i] = ch;
                        if (vis.count(str) == 0 && hash.count(str))
                        {
                            if (str == endGene)return count;
                            q.push(str); vis.insert(str);
                        }
                    }
                }
            }
        }
        return -1;
    }
};


//84. 单词接⻰

class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        unordered_set<string> hash;
        for (auto s : wordList)
        {
            hash.insert(s);
        }
        if (hash.count(endWord) == 0)return 0;
        unordered_set<string> vis;
        int count = 0;
        string t = "abcdefghijklmnopqrstuvwxyz";

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        while (q.size())
        {
            count++;
            int sz = q.size();

            for (int i = 0; i < sz; i++)
            {
                auto tmp = q.front();
                q.pop();

                for (int j = 0; j < endWord.size(); j++)
                {
                    for (auto ch : t)
                    {
                        string str = tmp;
                        str[j] = ch;
                        if (hash.count(str) && vis.count(str) == 0)
                        {
                            if (str == endWord)
                            {
                                return count + 1;
                            }
                            q.push(str);
                            vis.insert(str);
                        }
                    }
                }
            }
        }
        return 0;
    }
};


//85. 为⾼尔夫比赛砍树


//a.先找出砍树的顺序；
//b.然后按照砍树的顺序，⼀个⼀个的⽤ bfs 求出最短路即可。

class Solution
{
    int m = 0, n = 0;
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        // 1.准备工作：找出砍树的顺序
        m = forest.size(), n = forest[0].size();
        vector<pair<int, int>> order;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (forest[i][j] > 1)
                {
                    order.push_back({ i,j });
                }
            }
        }

        sort(order.begin(), order.end(), [&](const pair<int, int>p1, const pair<int, int>p2)
            {
                return forest[p1.first][p1.second] < forest[p2.first][p2.second];
            });

        // 2.按照顺序砍树
        int ret = 0;
        int bx = 0, by = 0;
        for (auto [a, b] : order)
        {
            int step = bfs(forest, bx, by, a, b);
            if (step == -1)return -1;
            ret += step;
            bx = a, by = b;
        }
        return ret;
    }

    bool vis[51][51];
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };

    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
    {
        int step = 0;
        memset(vis, 0, sizeof(vis));
        if (ex == bx && ey == by)
        {
            return 0;
        }
        queue<pair<int, int>> q;
        q.push({ bx,by });
        vis[bx][by] = true;
        while (q.size())
        {
            int sz = q.size();
            step++;
            while (sz--)
            {
                auto [a, b] = q.front(); q.pop();
                for (int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] != 0 && vis[x][y] == false)
                    {
                        if (x == ex && y == ey)
                        {
                            return step;
                        }
                        q.push({ x,y });
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};


//---------------------------------------------------------多源 BFS-------------------------------------------------------------------------

//86. 01 矩阵

//从 0 开始层序遍历，并且记录遍历的层数。当第⼀次碰到 1 的时候，当前的层数就是这个 1 离 0 的最短距离。

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
    {
        int m = mat.size(), n = mat[0].size();
        // dist[i][j] == -1 表⽰：没有搜索过
        // dist[i][j] != -1 表⽰：最短距离
        vector<vector<int>> dist(m, vector<int>(n, -1));

        queue<pair<int, int>> q;
        // 1. 把所有的源点加⼊到队列中
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 0)
                {
                    q.push({ i,j });
                    dist[i][j] = 0;
                }
            }
        }

        // 2. ⼀层⼀层的往外扩
        while (q.size())
        {
            auto [a, b] = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;//不用一层一层往外扩的原因 直接用上一层的步数+1
                    q.push({ x,y });
                }
            }
        }
        return dist;
    }
};


//87. ⻜地的数量

//正难则反：
//从边上的 1 开始搜索，把与边上 1 相连的联通区域全部标记⼀下；
//然后再遍历⼀遍矩阵，看看哪些位置的 1 没有被标记即可标记的时候，可以⽤「多源 bfs 」解决。

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    int numEnclaves(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));

        queue<pair<int, int>> q;

        //1.将边缘的1加入到队列
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
                {
                    if (grid[i][j] == 1)
                    {
                        q.push({ i,j });
                        vis[i][j] = 1;
                    }

                }
            }
        }

        while (q.size())
        {
            auto [a, b] = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && vis[x][y] == 0)
                {
                    q.push({ x,y });
                    vis[x][y] = 1;
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && vis[i][j] == 0)
                {
                    ret++;
                }
            }
        }
        return ret;
    }
};


//88. 地图中的最⾼点

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
    {
        int m = isWater.size(), n = isWater[0].size();

        vector<vector<int>> ret(m, vector<int>(n, -1));
        queue<pair<int, int>> q;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (isWater[i][j] == 1 && ret[i][j] == -1)
                {
                    q.push({ i,j });
                    ret[i][j] = 0;
                }
            }
        }
        while (q.size())
        {
            auto [a, b] = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && ret[x][y] == -1)
                {
                    q.push({ x,y });
                    ret[x][y] = ret[a][b] + 1;
                }
            }
        }
        return ret;
    }
};


//89. 地图分析

class Solution
{
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
public:
    int maxDistance(vector<vector<int>>& grid)
    {
        int m = grid.size(), n = grid[0].size();
        int ret = -1;
        queue<pair<int, int>> q;
        vector<vector<int>> dist(m, vector<int>(n, -1));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && dist[i][j] == -1)
                {
                    q.push({ i,j });
                    dist[i][j] = 0;
                }
            }
        }
        while (q.size())
        {
            auto [a, b] = q.front(); q.pop();
            for (int i = 0; i < 4; i++)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
                {
                    dist[x][y] = dist[a][b] + 1;
                    q.push({ x,y });
                    ret = max(ret, dist[x][y]);
                }
            }
        }
        return ret;
    }
};


//--------------------------------------------------------------BFS 解决拓扑排序---------------------------------------------------------

//90. 课程表

//a.将所有⼊度为 0 的点加⼊到队列中；
//b.当队列不空的时候，⼀直循环：
//i.取出队头元素；
//ii.将于队头元素相连的顶点的⼊度 - 1；
//iii.然后判断是否减成 0, 。如果减成 0，就加⼊到队列中。

class Solution
{
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites)
    {
        //准备工作
        unordered_map<int, vector<int>> egdes;//记录边
        vector<int> ins(n);//记录入度

        // 1. 建图
        for (auto e : prerequisites)
        {
            int a = e[0], b = e[1];
            //b->a
            egdes[b].push_back(a);
            ins[a]++;
        }

        // 2. 拓扑排序
        // 把所有⼊度为 0 的点加⼊到队列中
        queue<int> q;
        for (int i = 0; i < n; i++)
        {
            if (ins[i] == 0)//入度为0
            {
                q.push(i);
            }
        }

        //bfs
        while (q.size())
        {
            auto a = q.front(); q.pop();
            for (int b : egdes[a])
            {
                ins[b]--;
                if (ins[b] == 0)
                {
                    q.push(b);
                }
            }
        }

        for (auto x : ins)
        {
            if (x)return false;
        }
        return true;
    }
};


//91. 课程表II

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites)
    {
        unordered_map<int, vector<int>> edges;
        vector<int> ins(n);
        vector<int > ret;

        for (auto e : prerequisites)
        {
            int a = e[0], b = e[1];
            //b->a
            edges[b].push_back(a);
            ins[a]++;
        }

        queue<int> q;

        for (int i = 0; i < n; i++)
        {
            if (ins[i] == 0)
            {
                q.push(i);
            }
        }

        while (q.size())
        {
            auto a = q.front(); q.pop();
            ret.push_back(a);
            for (auto b : edges[a])
            {
                ins[b]--;
                if (ins[b] == 0)
                {
                    q.push(b);
                }
            }
        }

        for (auto x : ins)
        {
            if (x)return {};
        }

        return ret;
    }
};


//92. ⽕星词典

//a.两层 for 循环枚举出所有的两个字符串的组合；
//b.然后利⽤指针，根据字典序规则找出信息。

class Solution
{
    unordered_map<char, unordered_set<char>> edges;
    unordered_map<char, int> ins;//要初始化
    int check = 0;
public:
    string alienOrder(vector<string>& words)
    {
        string ret;
        for (auto s : words)
        {
            for (auto ch : s)
            {
                ins[ch] = 0;
            }
        }
        int n = words.size();

        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if (check == 1)return "";
            }
        }
        queue<char> q;
        for (auto [a, b] : ins)
        {
            if (b == 0)
            {
                q.push(a);
            }
        }

        while (q.size())
        {
            auto ch = q.front(); q.pop();
            ret += ch;
            for (auto s : edges[ch])
            {
                if (--ins[s] == 0)
                {
                    q.push(s);
                }
            }
        }
        for (auto [a, b] : ins)
        {
            if (b != 0)return "";
        }
        return ret;
    }

    void add(string s1, string s2)
    {
        int i = 0;
        int n = min(s1.size(), s2.size());
        for (; i < n; i++)
        {
            if (s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i];
                if (!edges.count(a) || !edges[a].count(b))//要判断有没有重复
                {
                    edges[a].insert(b);
                    ins[b]++;
                }
                break;// ✅ 必须加
            }

        }
        if (i == s2.size() && i < s1.size())
        {
            check = 1;
        }
    }
};